/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package test;

import test.tst.CharUtility;
import java.util.LinkedList;

/**
 * Implementation of ternary search tree. A Ternary Search Tree is a data structure that behaves
 * in a manner that is very similar to a HashMap.
 */
public class TernarySearchTreeModified {

    /**
     * The TST root node
     */
    private TSTNode rootNode;
    /**
     * The default number of return values
     */
    private int defaultNumReturnValues = -1;
    /**
     * The last number of values returned,
     * convenience variable for matchPrefix and sortKeys methods
     */
    private int lastNumberOfReturnValues;
    /**
     * The minimum string similarity value
     */
    private double minStringLengthSimilarity = 0.0;
    //
    private LinkedList matchResult;
    private StringBuffer matchBuffer;
    private boolean matchListAction;
    private int matchNumReturnValues;
    private String matchKey;
    private int matchDiff;
    private int maxMatchDiff = 4;
    private int searchMaxDepth = -1;

    /**
     * Stores value in the TernarySearchTree. The value may be retrieved using key.
     *
     * @param key   A string that indexes the object to be stored.
     * @param value The object to be stored in the tree.
     */
    public void put(String key, Object value) {
        getOrCreateNode(key).data = value;
    }

    /**
     * Retrieve the object indexed by key.
     *
     * @param key A String index.
     * @return Object The object retrieved from the TernarySearchTree.
     */
    public Object get(String key) {
        TSTNode node = getNode(key);
        if (node == null) {
            return null;
        }
        return node.data;
    }

    /**
     * Removes value indexed by key. Also removes all nodes that are rendered unnecessary by the removal of this data.
     *
     * @param key A string that indexes the object to be removed from the tree.
     */
    public void remove(String key) {
        deleteNode(getNode(key));
    }

    /**
     * Sets default maximum number of values returned from matchPrefix, matchPrefixString,
     * matchAlmost, and matchAlmostString methods.
     *
     * @param num The number of values that will be returned when calling the methods above. Set
     *            this to -1 to get an unlimited number of return values. Note that
     *            the methods mentioned above provide overloaded versions that allow you to specify the maximum number of
     *            return values, in which case this value is temporarily overridden.
     */
    public void setNumReturnValues(int num) {
        defaultNumReturnValues = (num < 0) ? -1 : num;
    }

    private int checkNumberOfReturnValues(int numReturnValues) {
        return ((numReturnValues < 0) ? -1 : numReturnValues);
    }

    /**
     * Returns the number of values returned by the last call to matchAlmostString or matchPrefixString methods.
     * (This is really just for the purposes of the demo applet.)
     * @return 
     */
    public int getLastNumReturnValues() {
        return lastNumberOfReturnValues;
    }

    /**
     * Returns the Node indexed by key, or null if that node doesn't exist. Search begins at root node.
     *
     * @param key An index that points to the desired node.
     * @return TSTNode The node object indexed by key. This object is an instance of an inner class
     *         named TernarySearchTree.TSTNode.
     */
    public TSTNode getNode(String key) {
        return getNode(key, rootNode);
    }

    /**
     * Returns the Node indexed by key, or null if that node doesn't exist. Search begins at root node.
     *
     * @param key       An index that points to the desired node.
     * @param startNode The top node defining the subtree to be searched.
     * @return TSTNode The node object indexed by key. This object is an instance of an inner class
     *         named TernarySearchTree.TSTNode.
     */
    protected TSTNode getNode(String key, TSTNode startNode) {
        if (key == null || startNode == null || key.length() == 0) {
            return null;
        }
        TSTNode currentNode = startNode;
        int charIndex = 0;
        while (true) {
            if (currentNode == null) {
                return null;
            }
            int charComp = CharUtility.compareCharsAlphabetically(key.charAt(charIndex), currentNode.splitchar);
            if (charComp == 0) {
                charIndex++;
                if (charIndex == key.length()) {
                    return currentNode;
                }
                currentNode = currentNode.relatives[TSTNode.EQKID];
            } else if (charComp < 0) {
                currentNode = currentNode.relatives[TSTNode.LOKID];
            } else {
                // charComp must be greater than zero
                currentNode = currentNode.relatives[TSTNode.HIKID];
            }
        }
    }

    /**
     * Returns alphabetical list of all keys in the tree that begin with prefix. Only keys for nodes having non-null data
     * are included in the list.
     *
     * @param prefix Each key returned from this method will begin with the characters in prefix.
     * @return LinkedList An implementation of a LinkedList that is java 1.1 compatible.
     */
    public LinkedList matchPrefix(String prefix) {
        return matchPrefix(prefix, defaultNumReturnValues);
    }

    /**
     * Returns alphabetical list of all keys in the tree that begin with prefix. Only keys for nodes having non-null data
     * are included in the list.
     *
     * @param prefix          Each key returned from this method will begin with the characters in prefix.
     * @param numReturnValues The maximum number of values returned from this method.
     * @return LinkedList An implementation of a LinkedList that is java 1.1 compatible.
     */
    public LinkedList matchPrefix(String prefix, int numReturnValues) {
        sortKeysNumReturnValues = checkNumberOfReturnValues(numReturnValues);
        sortKeysResult = new LinkedList();
        TSTNode startNode = getNode(prefix);
        if (startNode == null) {
            return sortKeysResult;
        }
        if (startNode.data != null) {
            sortKeysResult.addLast(getKey(startNode));
            sortKeysNumReturnValues--;
        }
        sortKeysList = true;
        sortKeysRecursion(startNode.relatives[TSTNode.EQKID]);
        return sortKeysResult;
    }

    /**
     * Returns alphabetical list of all keys in the tree that begin with prefix. Only keys for nodes having non-null data
     * are included in the list.
     *
     * @param prefix Each key returned from this method will begin with the characters in prefix.
     * @return String A string representation of all keys matching the argument prefix. Keys are delimited with the newline
     *         char ('\n').
     */
    public String matchPrefixString(String prefix) {
        return matchPrefixString(prefix, defaultNumReturnValues);
    }

    /**
     * Returns alphabetical list of all keys in the tree that begin with prefix. Only keys for nodes having non-null data
     * are included in the list.
     *
     * @param prefix          Each key returned from this method will begin with the characters in prefix.
     * @param numReturnValues The maximum number of values returned from this method.
     * @return String A string representation of all keys matching the argument prefix. Keys are delimited with the newline
     *         char ('\n').
     */
    public String matchPrefixString(String prefix, int numReturnValues) {
        TSTNode startNode = getNode(prefix);
        if (startNode == null) {
            return "";
        }
        sortKeysNumReturnValues = checkNumberOfReturnValues(numReturnValues);
        lastNumberOfReturnValues = sortKeysNumReturnValues;
        sortKeysBuffer = new StringBuffer();
        if (startNode.data != null) {
            sortKeysBuffer.append(getKey(startNode) + "\n");
            sortKeysNumReturnValues--;
        }
        sortKeysList = false;
        sortKeysRecursion(startNode.relatives[TSTNode.EQKID]);
        int bufferLength = sortKeysBuffer.length();
        if (bufferLength > 0) {
            sortKeysBuffer.setLength(bufferLength - 1); // delete the final \n
        }
        lastNumberOfReturnValues = lastNumberOfReturnValues - sortKeysNumReturnValues;
        return sortKeysBuffer.toString();
    }
    private LinkedList sortKeysResult;      // convenience variable for matchPrefix and sortKeys methods
    private boolean sortKeysList;      // convenience variable for matchPrefix, matchPrefixString and sortKeys methods
    private StringBuffer sortKeysBuffer;      // convenience variable for matchPrefixString and sortKeys methods
    private int sortKeysNumReturnValues;         // convenience variable for matchPrefix and sortKeys methods

    /* Returns keys sorted in alphabetical order. Includes currentNode and all nodes connected to currentNode. Sorted keys will
     *  be appended to end of result list. (result may be empty when this method is invoked, but may not be null.)
     */
    private void sortKeysRecursion(TSTNode currentNode) {
        if (currentNode == null) {
            return;
        }
        sortKeysRecursion(currentNode.relatives[TSTNode.LOKID]);
        if (sortKeysNumReturnValues == 0) {
            return;
        }
        if (currentNode.data != null) {
            if (sortKeysList) {
                sortKeysResult.addLast(getKey(currentNode));
            } else {
                sortKeysBuffer.append(getKey(currentNode) + "\n");
            }
            sortKeysNumReturnValues--;
        }
        sortKeysRecursion(currentNode.relatives[TSTNode.EQKID]);
        sortKeysRecursion(currentNode.relatives[TSTNode.HIKID]);
    }

    /**
     * Returns keys sorted in alphabetical order. Includes startNode and all nodes connected to startNode.
     * Number of keys returned is limited to numReturnValues. To get a list that isn't limited in size,
     * set numReturnValues to -1.
     *
     * @param startNode       The top node defining the subtree to be searched.
     * @param numReturnValues The maximum number of values returned from this method.
     * @return LinkedList An implementation of a LinkedList that is java 1.1 compatible.
     */
    protected LinkedList sortKeys(TSTNode startNode, int numReturnValues) {
        sortKeysNumReturnValues = checkNumberOfReturnValues(numReturnValues);
        sortKeysResult = new LinkedList();
        sortKeysRecursion(startNode);
        return sortKeysResult;
    }

    /**
     * 
     * @param numReturnValues
     * @return
     */
    public String sortKeysString(int numReturnValues) {
        return sortKeysString(rootNode, numReturnValues);
    }

    /**
     * 
     * @return
     */
    public String sortKeysString() {
        return sortKeysString(rootNode, defaultNumReturnValues);
    }

    /**
     * Returns keys sorted in alphabetical order, returning a result of type String. Includes startNode
     * and all nodes connected to startNode. Number of keys returned is limited to numReturnValues. To get
     * a list that isn't limited in size, set numReturnValues to -1.
     *
     * @param startNode       The top node defining the subtree to be searched.
     * @param numReturnValues The maximum number of values returned from this method.
     * @return String A string representation of keys in alphabetical order.
     */
    public String sortKeysString(TSTNode startNode, int numReturnValues) {
        if (startNode == null) {
            return new String("");
        }
        sortKeysNumReturnValues = checkNumberOfReturnValues(numReturnValues);
        lastNumberOfReturnValues = sortKeysNumReturnValues;
        sortKeysBuffer = new StringBuffer();
        if (startNode.data != null) {
            sortKeysBuffer.append(getKey(startNode) + "\n");
            sortKeysNumReturnValues--;
        }
        sortKeysList = false;
        sortKeysRecursion(startNode);
        int bufferLength = sortKeysBuffer.length();
        if (bufferLength > 0) {
            sortKeysBuffer.setLength(bufferLength - 1); // delete the final \n
        }
        lastNumberOfReturnValues = lastNumberOfReturnValues - sortKeysNumReturnValues;
        return sortKeysBuffer.toString();
    }

    /**
     * Returns a list of keys that almost match argument key.
     * Keys returned will have exactly diff characters that do not match the target key,
     * where diff is equal to the last value passed in as an argument to the setMatchDiff
     * method. If the matchAlmost method is called before the setMatchDiff method has been
     * called for the first time, then diff = 0.
     *
     * @param key The target key.
     * @return LinkedList An implementation of a LinkedList that is java 1.1 compatible.
     */
    public LinkedList matchAlmost(String key) {
        return matchAlmost(key, defaultNumReturnValues);
    }

    /**
     * Returns a list of keys that almost match argument key.
     * Keys returned will have exactly diff characters that do not match the target key,
     * where diff is equal to the last value passed in as an argument to the setMatchDiff
     * method. If the matchAlmost method is called before the setMatchDiff method has been
     * called for the first time, then diff = 0.
     *
     * @param key             The target key.
     * @param numReturnValues The maximum number of values returned by this method.
     * @return LinkedList An implementation of a LinkedList that is java 1.1 compatible.
     */
    protected LinkedList matchAlmost(String key, int numReturnValues) {
        matchListAction = true;
        matchNumReturnValues = checkNumberOfReturnValues(numReturnValues);
        matchResult = new LinkedList();
        matchKey = key;
        matchAlmostRecursion(rootNode, 0, matchDiff);
        return matchResult;
    }

    /**
     * Returns a String representation of keys that almost match argument key.
     * Keys returned will have exactly diff characters that do not match the target key,
     * where diff is equal to the last value passed in as an argument to the setMatchDiff
     * method. If the matchAlmost method is called before the setMatchDiff method has been
     * called for the first time, then diff = 0.
     *
     * @param key The target key.
     * @return String A String representation of keys that almost match the target key. Keys are
     *         delimited by the newline char ('\n').
     */
    public String matchAlmostString(String key) {
        return matchAlmostString(key, defaultNumReturnValues);
    }

    /**
     * Returns a String representation of keys that almost match argument key.
     * Keys returned will have exactly diff characters that do not match the target key,
     * where diff is equal to the last value passed in as an argument to the setMatchDiff
     * method. If the matchAlmost method is called before the setMatchDiff method has been
     * called for the first time, then diff = 0.
     *
     * @param key             The target key.
     * @param numReturnValues The maximum number of values returned by this method.
     * @return String A String representation of keys that almost match the target key. Keys are
     *         delimited by the newline char ('\n').
     */
    protected String matchAlmostString(String key, int numReturnValues) {
        matchListAction = false;
        matchNumReturnValues = checkNumberOfReturnValues(numReturnValues);
        lastNumberOfReturnValues = matchNumReturnValues;
        matchBuffer = new StringBuffer();
        matchKey = key;
        matchAlmostRecursion(rootNode, 0, matchDiff);
        int bufferLength = matchBuffer.length();
        if (bufferLength > 0) {
            matchBuffer.setLength(bufferLength - 1); // delete the final \n
        }
        lastNumberOfReturnValues = lastNumberOfReturnValues - matchNumReturnValues;
        return matchBuffer.toString();
    }

    private void matchAlmostRecursion(TSTNode currentNode, int charIndex, int d) {
        if ((currentNode == null) || (d < 0) || (matchNumReturnValues == 0) || (charIndex >= matchKey.length())) {
            return;
        }

        int charComp = CharUtility.compareCharsAlphabetically(matchKey.charAt(charIndex), currentNode.splitchar);

        // low branch
        if ((d > 0) || (charComp < 0)) {
            matchAlmostRecursion(currentNode.relatives[TSTNode.LOKID], charIndex, d);
        }

        //equal branch
        int nextD = (charComp == 0) ? d : d - 1;
        if ((matchKey.length() == charIndex + 1) && (nextD == 0) && (currentNode.data != null)) {
            // Note: the condition nextD == 0 causes keys to be included in the result only if they have exactly matchDiff number
            // of mismatched letters
            // If instead the condition nextD >= 0 is used, then all keys having up to and including matchDiff mismatched letters
            // will be included in the result (including a key that is exactly the same as the target string).
            if (matchListAction) {
                matchResult.addLast(getKey(currentNode));
            } else {
                matchBuffer.append(getKey(currentNode) + "\n");
            }
            matchNumReturnValues--;
        }
        matchAlmostRecursion(currentNode.relatives[TSTNode.EQKID], charIndex + 1, nextD);

        // hi branch
        if ((d > 0) || (charComp > 0)) {
            matchAlmostRecursion(currentNode.relatives[TSTNode.HIKID], charIndex, d);
        }
    }

    /**
     * Sets the number of characters by which words can differ from target word when
     * calling matchAlmost or matchAlmostString methods. Arguments
     * less than 1 will set the char difference to 1, and arguments greater than 4
     * will set the char difference to 4.
     *
     * @param diff The number of characters by which words can differ from target word.
     */
    public void setMatchDiff(int diff) {
        if (diff < 0) {
            matchDiff = 0;
        } else if (diff > maxMatchDiff) {
            matchDiff = maxMatchDiff;
        } else {
            matchDiff = diff;
        }
    }

    /**
     * Returns the Node indexed by key, creating that node if it doesn't exist, and creating any required.
     * intermediate nodes if they don't exist.
     *
     * @param key A string that indexes the node that is returned.
     * @return TSTNode The node object indexed by key. This object is an instance of an inner class
     *         named TernarySearchTree.TSTNode.
     * @throws NullPointerException
     * @throws IllegalArgumentException  
     */
    protected TSTNode getOrCreateNode(String key) throws NullPointerException, IllegalArgumentException {
        if (key == null) {
            throw new NullPointerException("attempt to get or create node with null key");
        }
        if (key.length() == 0) {
            throw new IllegalArgumentException("attempt to get or create node with key of zero length");
        }
        if (rootNode == null) {
            rootNode = new TSTNode(key.charAt(0), null);
        }
        TSTNode currentNode = rootNode;
        int charIndex = 0;
        while (true) {
            int charComp = CharUtility.compareCharsAlphabetically(key.charAt(charIndex), currentNode.splitchar);
            if (charComp == 0) {
                charIndex++;
                if (charIndex == key.length()) {
                    return currentNode;
                }
                if (currentNode.relatives[TSTNode.EQKID] == null) {
                    currentNode.relatives[TSTNode.EQKID] = new TSTNode(key.charAt(charIndex), currentNode);
                }
                currentNode = currentNode.relatives[TSTNode.EQKID];
            } else if (charComp < 0) {
                if (currentNode.relatives[TSTNode.LOKID] == null) {
                    currentNode.relatives[TSTNode.LOKID] = new TSTNode(key.charAt(charIndex), currentNode);
                }
                currentNode = currentNode.relatives[TSTNode.LOKID];
            } else {
                // charComp must be greater than zero
                if (currentNode.relatives[TSTNode.HIKID] == null) {
                    currentNode.relatives[TSTNode.HIKID] = new TSTNode(key.charAt(charIndex), currentNode);
                }
                currentNode = currentNode.relatives[TSTNode.HIKID];
            }
        }
    }

    /*  Deletes the node passed in as an argument to this method. If this node has non-null data, then both the node and the data will be deleted.
     *   Also deletes any other nodes in the tree that are no longer needed after the deletion of the node first passed in as an argument to this method.
     */
    private void deleteNode(TSTNode nodeToDelete) {
        if (nodeToDelete == null) {
            return;
        }
        nodeToDelete.data = null;
        while (nodeToDelete != null) {
            nodeToDelete = deleteNodeRecursion(nodeToDelete);
        }
    }

    private TSTNode deleteNodeRecursion(TSTNode currentNode) {
        // To delete a node, first set its data to null, then pass it into this method, then pass the node returned by this method into this method
        // (make sure you don't delete the data of any of the nodes returned from this method!)
        // and continue in this fashion until the node returned by this method is null.
        // The TSTNode instance returned by this method will be next node to be operated on by deleteNodeRecursion.
        // (This emulates recursive method call while avoiding the JVM overhead normally associated with a recursive method.)
        if (currentNode == null) {
            return null;
        }
        if (currentNode.relatives[TSTNode.EQKID] != null || currentNode.data != null) {
            return null;  // can't delete this node if it has a non-null eq kid or data
        }
        TSTNode currentParent = currentNode.relatives[TSTNode.PARENT];

        // if we've made it this far, then we know the currentNode isn't null, but its data and equal kid are null, so we can delete the current node
        // (before deleting the current node, we'll move any lower nodes higher in the tree)
        boolean lokidNull = currentNode.relatives[TSTNode.LOKID] == null;
        boolean hikidNull = currentNode.relatives[TSTNode.HIKID] == null;

        // now find out what kind of child current node is
        int childType;
        if (currentParent.relatives[TSTNode.LOKID] == currentNode) {
            childType = TSTNode.LOKID;
        } else if (currentParent.relatives[TSTNode.EQKID] == currentNode) {
            childType = TSTNode.EQKID;
        } else if (currentParent.relatives[TSTNode.HIKID] == currentNode) {
            childType = TSTNode.HIKID;
        } else {
            // if this executes, then current node is root node
            rootNode = null;
            return null;
        }

        if (lokidNull && hikidNull) {
            // if we make it to here, all three kids are null and we can just delete this node
            currentParent.relatives[childType] = null;
            return currentParent;
        }
        // if we make it this far, we know that EQKID is null, and either HIKID or LOKID is null, or both HIKID and LOKID are NON-null
        if (lokidNull) {
            currentParent.relatives[childType] = currentNode.relatives[TSTNode.HIKID];
            currentNode.relatives[TSTNode.HIKID].relatives[TSTNode.PARENT] = currentParent;
            return currentParent;
        }
        if (hikidNull) {
            currentParent.relatives[childType] = currentNode.relatives[TSTNode.LOKID];
            currentNode.relatives[TSTNode.LOKID].relatives[TSTNode.PARENT] = currentParent;
            return currentParent;
        }

        int deltaHi = currentNode.relatives[TSTNode.HIKID].splitchar - currentNode.splitchar;
        int deltaLo = currentNode.splitchar - currentNode.relatives[TSTNode.LOKID].splitchar;
        int movingKid;
        TSTNode targetNode;
        // if deltaHi is equal to deltaLo, then choose one of them at random, and make it "further away" from the current node's splitchar
        if (deltaHi == deltaLo) {
            if (Math.random() < 0.5) {
                deltaHi++;
            } else {
                deltaLo++;
            }
        }

        if (deltaHi > deltaLo) {
            movingKid = TSTNode.HIKID;
            targetNode = currentNode.relatives[TSTNode.LOKID];
        } else {
            movingKid = TSTNode.LOKID;
            targetNode = currentNode.relatives[TSTNode.HIKID];
        }

        while (targetNode.relatives[movingKid] != null) {
            targetNode = targetNode.relatives[movingKid];
        }
        // now targetNode.relatives[movingKid] is null, and we can put the moving kid into it.
        targetNode.relatives[movingKid] = currentNode.relatives[movingKid];

        // now we need to put the target node where the current node used to be
        currentParent.relatives[childType] = targetNode;
        targetNode.relatives[TSTNode.PARENT] = currentParent;

        if (!lokidNull) {
            currentNode.relatives[TSTNode.LOKID] = null;
        }
        if (!hikidNull) {
            currentNode.relatives[TSTNode.HIKID] = null;
        }

        // note that the statements above ensure currentNode is completely dereferenced, and so it will be garbage collected

        return currentParent;
    }

    /**
     * An inner class of TernarySearchTree that represents a node in the tree.
     */
    protected class TSTNode {

        /**
         * 
         */
        /**
         * 
         */
        /**
         * 
         */
        /**
         * 
         */
        protected static final int PARENT = 0, LOKID = 1, EQKID = 2, HIKID = 3; // index values for accessing relatives array
        /**
         * 
         */
        protected char splitchar;
        /**
         * 
         */
        protected TSTNode[] relatives = new TSTNode[4];
        /**
         * 
         */
        protected Object data;

        /**
         * 
         * @param splitchar
         * @param parent
         */
        protected TSTNode(char splitchar, TSTNode parent) {
            this.splitchar = splitchar;
            relatives[PARENT] = parent;
        }
    }
    private StringBuffer getKeyBuffer = new StringBuffer();   // convenience variable for getKey method

    /**
     * Returns the key that indexes the node argument.
     *
     * @param node The node whose index is to be calculated.
     * @return String The string that indexes the node argument.
     */
    protected String getKey(TSTNode node) {
        getKeyBuffer.setLength(0);
        getKeyBuffer.append(node.splitchar);
        TSTNode currentNode, lastNode;
        currentNode = node.relatives[TSTNode.PARENT];
        lastNode = node;
        while (currentNode != null) {
            if (currentNode.relatives[TSTNode.EQKID] == lastNode) {
                getKeyBuffer.append(currentNode.splitchar);
            }
            lastNode = currentNode;
            currentNode = currentNode.relatives[TSTNode.PARENT];
        }
        getKeyBuffer.reverse();
        return getKeyBuffer.toString();
    }
    private int numNodes;   // convenience variable for numNodes methods
    private boolean checkData;   // convenience variable for numNodes methods

    /**
     * Returns the total number of nodes in the tree. Counts nodes whether or not they have data.
     *
     * @return int The total number of nodes in the tree.
     */
    public int numNodes() {
        return numNodes(rootNode);
    }

    /**
     * Returns the total number of nodes in the subtree below and including startingNode. Counts nodes whether or not they have data.
     *
     * @param startingNode The top node of the subtree. The node that defines the subtree.
     * @return int The total number of nodes in the subtree.
     */
    protected int numNodes(TSTNode startingNode) {
        numNodes = 0;
        checkData = false;
        recursiveNodeCalculator(startingNode);
        return numNodes;
    }

    /**
     * Returns the number of nodes in the tree that have non-null data.
     *
     * @return int The number of nodes in the tree that have non-null data.
     */
    public int numDataNodes() {
        return numDataNodes(rootNode);
    }

    /**
     * Returns the number of nodes in the subtree below and including startingNode. Counts only nodes that have non-null data.
     *
     * @param startingNode The top node of the subtree. The node that defines the subtree.
     * @return int The total number of nodes in the subtree.
     */
    protected int numDataNodes(TSTNode startingNode) {
        numNodes = 0;
        checkData = true;
        recursiveNodeCalculator(startingNode);
        return numNodes;
    }

    private void recursiveNodeCalculator(TSTNode currentNode) {
        if (currentNode == null) {
            return;
        }
        recursiveNodeCalculator(currentNode.relatives[TSTNode.LOKID]);
        recursiveNodeCalculator(currentNode.relatives[TSTNode.EQKID]);
        recursiveNodeCalculator(currentNode.relatives[TSTNode.HIKID]);
        if (checkData) {
            if (currentNode.data != null) {
                numNodes++;
            }
        } else {
            numNodes++;
        }
    }

    /**
     * Prints entire tree structure to standard output, beginning with the root node and workind down.
     */
    public void printTree() {
        System.out.println("");
        if (rootNode == null) {
            System.out.println("tree is empty");
            return;
        }
        System.out.println("Here's the entire tree structure:");
        printNodeRecursion(rootNode);
    }

    /**
     * Prints subtree structure to standard output, beginning with startingNode and workind down.
     * @param startingNode 
     */
    protected void printTree(TSTNode startingNode) {
        System.out.println("");
        if (rootNode == null) {
            System.out.println("subtree is empty");
            return;
        }
        System.out.println("Here's the entire subtree structure:");
        printNodeRecursion(startingNode);
    }

    /**
     * Recursive method used to print out tree or subtree structure.
     */
    private void printNodeRecursion(TSTNode currentNode) {
        if (currentNode == null) {
            return;
        }
        System.out.println("");
        System.out.println("( keys are delimited by vertical lines: |example key| )");
        System.out.println("info for node   |" + getKey(currentNode) + "|         node data: " + currentNode.data);
        if (currentNode.relatives[TSTNode.PARENT] == null) {
            System.out.println("parent null");
        } else {
            System.out.println("parent key   |" + getKey(currentNode.relatives[TSTNode.PARENT]) + "|       parent data: " + currentNode.relatives[TSTNode.PARENT].data);
        }
        if (currentNode.relatives[TSTNode.LOKID] == null) {
            System.out.println("lokid null");
        } else {
            System.out.println("lokid key   |" + getKey(currentNode.relatives[TSTNode.LOKID]) + "|       lo kid data: " + currentNode.relatives[TSTNode.LOKID].data);
        }
        if (currentNode.relatives[TSTNode.EQKID] == null) {
            System.out.println("eqkid null");
        } else {
            System.out.println("eqkid key   |" + getKey(currentNode.relatives[TSTNode.EQKID]) + "|       equal kid data: " + currentNode.relatives[TSTNode.EQKID].data);
        }
        if (currentNode.relatives[TSTNode.HIKID] == null) {
            System.out.println("hikid null");
        } else {
            System.out.println("hikid key   |" + getKey(currentNode.relatives[TSTNode.HIKID]) + "|       hi kid data: " + currentNode.relatives[TSTNode.HIKID].data);
        }
        printNodeRecursion(currentNode.relatives[TSTNode.LOKID]);
        printNodeRecursion(currentNode.relatives[TSTNode.EQKID]);
        printNodeRecursion(currentNode.relatives[TSTNode.HIKID]);
    }

    //
    // Extensions by Igor Tavcar
    //
    private enum MatchDeepState {

        search, scan, collect
    };

    /**
     * 
     * @param key
     * @return
     */
    public LinkedList matchDeep(String key) {
        return matchDeep(key, defaultNumReturnValues, 0.0);
    }

    /**
     * 
     * @param key
     * @param maxDepth
     * @param minSimilarity
     * @return
     */
    public LinkedList matchDeep(String key, int maxDepth, double minSimilarity) {
        return matchDeep(key, defaultNumReturnValues, maxDepth, minSimilarity);
    }

    /**
     * 
     * @param key
     * @param numReturnValues
     * @param maxDepth
     * @param minSimilarity
     * @return
     */
    public LinkedList matchDeep(String key, int numReturnValues, int maxDepth, double minSimilarity) {
        matchResult = new LinkedList();
        matchNumReturnValues = checkNumberOfReturnValues(numReturnValues);
        matchKey = key;
        searchMaxDepth = maxDepth;
        minStringLengthSimilarity = minSimilarity;
        if (searchMaxDepth == 0) {
            collectPrefix(key, numReturnValues);
        } else {
            matchDeepRecursion(rootNode, 0, 0, MatchDeepState.search);
        }

        matchInsidePath();
        return matchResult;
    }

    private void collectPrefix(String key, int numReturnValues) {
        LinkedList keys = matchPrefix(key, numReturnValues);
        for (Object o : keys) {
            final String currKey = (String) o;
            if (checkStringLengthSimilarity(currKey.length(), key.length())) {
                matchResult.addLast(get(currKey));
            }
        }
    }

    private void matchInsidePath() {
        int n = matchKey.length();
        for (int i = 1; i < n; i++) {
            matchInsidePath(i, n, n);
        }

        for (int j = n - 1; j >= 1; --j) {
            matchInsidePath(0, j, n);
        }

    }

    private void matchInsidePath(int i, int j, int n) {
        if (!checkStringLengthSimilarity(n, j - i)) {
            return;
        }

        String path = matchKey.substring(i, j);

        TSTNode currentNode = rootNode;
        int charIndex = 0;
        while (true) {
            if (currentNode == null || matchNumReturnValues == 0) {
                return;
            }

            int charComp = CharUtility.compareCharsAlphabetically(path.charAt(charIndex), currentNode.splitchar);
            if (charComp == 0) {
                charIndex++;
                if (currentNode.data != null) {
                    String key = getKey(currentNode);
                    if (checkStringLengthSimilarity(matchKey.length(), key.length())) {
                        if (!matchResult.contains(currentNode.data)) {
                            matchResult.addLast(currentNode.data);
                            --matchNumReturnValues;
                        }
                    }
                }
                if (charIndex == path.length()) {
                    return;
                }
                currentNode = currentNode.relatives[TSTNode.EQKID];
            } else if (charComp < 0) {
                currentNode = currentNode.relatives[TSTNode.LOKID];
            } else {
                currentNode = currentNode.relatives[TSTNode.HIKID];
            }
        }
    }

    private void matchDeepRecursion(TSTNode currentNode, int currentDepth, int charIndex, MatchDeepState state) {
        if ((currentNode == null) || (matchNumReturnValues == 0) || (charIndex >= matchKey.length())) {
            return;
        }

        if (state == MatchDeepState.search && searchMaxDepth >= 0 && currentDepth > searchMaxDepth) {
            return;
        }

        if (state == MatchDeepState.collect) {
            if (currentNode.data != null) {
                String key = getKey(currentNode);
                if (checkStringLengthSimilarity(matchKey.length(), key.length())) {
                    matchResult.addLast(currentNode.data);
                    --matchNumReturnValues;
                }
            }
            matchDeepRecursion(currentNode.relatives[TSTNode.EQKID], -1, -1, MatchDeepState.collect);
            matchDeepRecursion(currentNode.relatives[TSTNode.LOKID], -1, -1, MatchDeepState.collect);
            matchDeepRecursion(currentNode.relatives[TSTNode.HIKID], -1, -1, MatchDeepState.collect);
            return;
        }

        int charComp = CharUtility.compareCharsAlphabetically(matchKey.charAt(charIndex), currentNode.splitchar);

        if (charComp < 0) {
            if (currentNode.relatives[TSTNode.LOKID] == null && state == MatchDeepState.scan) {
                matchDeepRecursion(currentNode.relatives[TSTNode.EQKID], currentDepth + 1, 0, MatchDeepState.search);
                matchDeepRecursion(currentNode.relatives[TSTNode.HIKID], currentDepth, 0, MatchDeepState.search);
            } else {
                if (state == MatchDeepState.scan) {
                    matchDeepRecursion(currentNode.relatives[TSTNode.LOKID], currentDepth, charIndex, state);
                    matchDeepRecursion(currentNode.relatives[TSTNode.EQKID], currentDepth + 1, charIndex, state);
                } else {
                    matchDeepRecursion(currentNode.relatives[TSTNode.LOKID], currentDepth, 0, MatchDeepState.search);
                    matchDeepRecursion(currentNode.relatives[TSTNode.EQKID], currentDepth + 1, 0, MatchDeepState.search);
                    matchDeepRecursion(currentNode.relatives[TSTNode.HIKID], currentDepth, 0, MatchDeepState.search);
                }
            }
        } else if (charComp > 0) {
            if (currentNode.relatives[TSTNode.HIKID] == null && state == MatchDeepState.scan) {
                matchDeepRecursion(currentNode.relatives[TSTNode.EQKID], currentDepth + 1, 0, MatchDeepState.search);
                matchDeepRecursion(currentNode.relatives[TSTNode.LOKID], currentDepth, 0, MatchDeepState.search);
            } else {
                if (state == MatchDeepState.scan) {
                    matchDeepRecursion(currentNode.relatives[TSTNode.HIKID], currentDepth, charIndex, state);
                    matchDeepRecursion(currentNode.relatives[TSTNode.EQKID], currentDepth + 1, charIndex, state);
                } else {
                    matchDeepRecursion(currentNode.relatives[TSTNode.HIKID], currentDepth, 0, MatchDeepState.search);
                    matchDeepRecursion(currentNode.relatives[TSTNode.EQKID], currentDepth + 1, 0, MatchDeepState.search);
                    matchDeepRecursion(currentNode.relatives[TSTNode.LOKID], currentDepth, 0, MatchDeepState.search);
                }
            }
        } else if (charComp == 0) {
            if (matchKey.length() == charIndex + 1) {
                if (currentNode.data != null) {
                    String key = getKey(currentNode);
                    if (checkStringLengthSimilarity(charIndex + 1, key.length())) {
                        matchResult.addLast(currentNode.data);
                        --matchNumReturnValues;
                    }
                }
                matchDeepRecursion(currentNode.relatives[TSTNode.EQKID], -1, -1, MatchDeepState.collect);
                matchDeepRecursion(currentNode.relatives[TSTNode.LOKID], currentDepth, 0, MatchDeepState.search);
                matchDeepRecursion(currentNode.relatives[TSTNode.HIKID], currentDepth, 0, MatchDeepState.search);
            } else {
                matchDeepRecursion(currentNode.relatives[TSTNode.EQKID], currentDepth + 1, charIndex + 1, MatchDeepState.scan);
                matchDeepRecursion(currentNode.relatives[TSTNode.LOKID], currentDepth, 0, MatchDeepState.search);
                matchDeepRecursion(currentNode.relatives[TSTNode.HIKID], currentDepth, 0, MatchDeepState.search);
            }
        }
    }

    private boolean checkStringLengthSimilarity(int len1, int len2) {
        int minLen = (len1 > len2 ? len2 : len1);

        int maxLen = (len1 > len2 ? len1 : len2);

        return ((((float) minLen) / maxLen) >= minStringLengthSimilarity);
    }

    public static void main(String[] args) {

        TernarySearchTreeModified tst = new TernarySearchTreeModified();
         tst.put("Alejo", 0);
        tst.put("ass", 55);
        tst.put("asd", 45);
        tst.put("asf", 75);
        LinkedList dll = tst.matchPrefix("as");
        for (Object object : dll) {
            System.out.println(""+object);
        }

        System.out.println(tst.numNodes());
        System.out.println(tst.get("Alejo"));
        System.out.println(tst.get("ass"));
        System.out.println(tst.get("asd"));
        System.out.println(tst.get("asf"));
        System.out.println(tst.get("22"));
        
        
    }
}
